package lab.exec;

import java.util.Arrays;

@SuppressWarnings("unchecked")
public class BalanceCaculator<T> {
	private QueueItem<T>[] buf = new QueueItem[20];
	private int startIndex = 0;;

	private int sum(QueueItem<T>[] a, int from, int to) {
		int sum = 0;
		for (int i = from; i < to; i++) {
			sum += a[i].size();
		}
		return sum;
	}

	private int selectValue(QueueItem<T>[] src, int idx, int size, boolean rm) {
		if (buf.length <= size) {
			QueueItem<T>[] temp = new QueueItem[buf.length + 1];
			System.arraycopy(buf, 0, temp, 0, size);
			buf = temp;
		}
		buf[size] = src[idx];
		if (rm) {
			for (int i = idx; i > startIndex; i--) {
				src[i] = src[i - 1];
			}
			startIndex++;
		} else {
			src[idx] = null;
		}
		return ++size;
	}

	private int selectNext(QueueItem<T>[] src, int idx, int avg) {
		int s = src[idx].size();
		if (s < 0) {
			return -1;
		}
		int size = 0;
		size = selectValue(src, idx, size, false);
		if (s >= avg || idx == startIndex) {
			return size;
		} else if (idx == startIndex + 1) {
			return selectValue(src, --idx, size, true);
		}
		idx--;
		int n1 = -1;
		int n2 = -1;
		while (idx >= startIndex) {
			int i1 = idx;
			if (n2 >= 0) {
				n1 = n2;
			} else {
				n1 = src[i1].size();
			}
			int i2 = i1 - 1;
			if (i2 >= startIndex) {
				n2 = src[i2].size();
			} else {
				n2 = -1;
			}
			int d1 = n1 + s - avg;
			int d2 = n2 + s - avg;
			if (d1 >= 0 && d2 <= 0) {
				if (d1 + d2 <= 0 || n2 < 0) {
					return selectValue(src, i1, size, true);
				} else {
					return selectValue(src, i2, size, true);
				}
			}
			if (d1 < 0) {
				s += n1;
				size = selectValue(src, i1, size, true);
				idx = i1;
			} else {
				idx = i2;
			}
		}
		return size;
	}

	public synchronized QueueItem<T>[][] balance(QueueItem<T>[] src, int processCount) {
		startIndex = 0;
		Arrays.sort(src);
		QueueItem<T>[][] ab = new QueueItem[processCount][];
		int pi = 0;
		for (int i = src.length - 1; i >= startIndex; i--) {
			int avg = sum(src, startIndex, i + 1) / (pi >= processCount ? processCount : processCount - pi);
			int size = selectNext(src, i, avg);
			if (size > 0) {
				QueueItem<T>[] a = new QueueItem[size];
				System.arraycopy(buf, 0, a, 0, size);
				if (pi >= processCount) {
					for (int j = 0; j < a.length; j++, pi++) {
						int ri = pi % processCount;
						QueueItem<T>[] t = ab[ri];
						QueueItem<T>[] _t = new QueueItem[t.length + 1];
						System.arraycopy(t, 0, _t, 0, t.length);
						_t[t.length] = a[j];
						ab[ri] = _t;
					}
				} else {
					ab[pi++] = a;
				}
			}
		}
		while (pi < processCount) {
			ab[pi++] = new QueueItem[0];
		}
		return ab;
	}
}

class QueueItem<T> implements Comparable<QueueItem<T>> {
	private ProcessQueue<T> queue = null;

	public QueueItem(ProcessQueue<T> queue) {
		this.queue = queue;
	}

	public int compareTo(QueueItem<T> o) {
		return queue.size() - o.size();
	}

	public ProcessQueue<T> getQueue() {
		return queue;
	}

	public int size() {
		return queue.size();
	}

	public String toString() {
		return "" + queue.size();
	}
}
